#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
  int data;
  struct LNode *next;
} LNode, *LinkList;

void CreateList(LinkList *L)
{
  *L = (LinkList)malloc(sizeof(LNode));
  if (*L == NULL)
  {
    printf("Memory allocation failed!\n");
    return;
  }
  (*L)->next = NULL;

  printf("请输入链表的元素（以-1结束）：\n");
  int value;
  while (1)
  {
    scanf("%d", &value);
    if (value == -1)
      break;

    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    if (newNode == NULL)
    {
      printf("Memory allocation failed!\n");
      return;
    }
    newNode->data = value;
    newNode->next = (*L)->next;
    (*L)->next = newNode;
  }
}

// 查找链表中间节点
LNode *FindMiddleElement(LinkList L)
{
  if (L == NULL || L->next == NULL)
    return NULL;

  LNode *slow = L->next; // 慢指针
  LNode *fast = L->next; // 快指针
  LNode *prev = NULL;    // 记录慢指针的前驱节点

  while (fast != NULL && fast->next != NULL)
  {
    fast = fast->next->next;  // 快指针每次走两步
    LNode *next = slow->next; // 记录慢指针的下一个节点
    slow->next = prev;        // 反转链表
    prev = slow;              // 更新前驱节点
    slow = next;              // 慢指针后移
  }

  // 如果链表长度为奇数，返回中间节点；如果为偶数，返回第二个中间节点
  return fast == NULL ? prev : slow;
}

// 循环输出
int main()
{
  LinkList L;
  CreateList(&L);

  printf("链表元素为：");
  LNode *current = L->next; // 跳过头节点
  while (current != NULL)
  {
    printf("%d ", current->data);
    current = current->next;
  }
  printf("\n");

  LNode *middle = FindMiddleElement(L);
  if (middle != NULL)
  {
    printf("链表中间元素为：%d\n", middle->data);
  }
  else
  {
    printf("链表为空或只有一个元素，无法找到中间元素。\n");
  }

  return 0;
}